[WC2019]数树(树形dp+多项式exp)
[WC2019]数树(树形dp+多项式exp)
Part1
相同边连接的点同一颜色,直接模拟即可
1 | namespace pt1{ |
Part2
相同边连接的点同一颜色,即在相同边构成的树上形成了若干联通块
很容易想到可以强制一些边保留,设保留 \(i\) 条边的方案数是 \(F_i\) ,则答案就是 \(\sum_i F_i\cdot y^{n-i}\)
考虑 \(dp\) 那些边相同,但是不好直接计算剩下边不同的方案,所以考虑计算最多有 \(i\) 条边相同的方案数,即
\[G_i=\sum_{j=i}C(j,i)F_j\]
二项式反演得到 \(F_i=\sum_{j=i}(-1)^{j-i}C(j,i)G_j\)
设分成了 \(m\) 个联通块,大小分别为 \(size_i\) ,则这些联通块随意构成树的方案数就是 \(n^{m-2}\cdot\prod size_i\)
根据上述性质可以写出一个简单的 \(O(n^4)\) 树形dp求得 \(G_i\) ,即 \(dp[i][j][k]\) 表示在 \(i\) 的子树里,有 \(j\) 条边相同,当前还剩下一个大小为 \(k\) 的联通块,每多转移一条相同边,系数是 \(\frac{1}{ny}\)
考虑优化 \(dp\)
联通块大小的问题,可以转化为每次在联通块里选择一个关键点的方案数, \(dp\) 第三维 \(0/1\) 表示当前联通块里是否已经选出了关键点
每次断开一个联通块时必须已经存在关键点
答案是
\(\sum_i F_i\cdot y^{n-i}\)
\(=\sum_i y^{n-i} \sum_{j=i}(-1)^{j-i}C(j,i)G_j\)
\(=y^n G_j\sum_{i=0}^j(-1)^{j-i}C(j,i)y^{-i}\)
发现右边的式子 \(\sum_0^j(-1)^{j-i}C(j,i)y^{-i}=(\frac{1}{y}-1)^j\)
那么直接把 \(\frac{1}{y}-1\) 带入作为保留一条边的转移系数,消去了第二维
那么这个 \(\text{dp}\) 可以被优化到 \(O(n)\)
\[ \ \]
1 | namespace pt2{ |
Part3
有了上面的 \(dp\) ,这一部分就简单多了,设分成了 \(m\) 个联通块,每个大小为 \(a_i\) ,则贡献为
\[\begin{aligned}\frac{n!\cdot a_i^{a_i-2}\cdot (n^{m-2})^2(\frac{1}{y}-1)^{n-m}(\frac{1}{n}^{n-m})^2\cdot a_i^2}{\prod a_i! m !}\end{aligned}\]
即枚举每个联通块生成树的数量,且需要考虑两棵树分别的联通块之间的连边数量,这一部分需要平方
很显然,可以直接对于 \([x^i]F(x)=\frac{1}{i!}\cdot (\frac{1}{n^2}\cdot (\frac{1}{y}-1))^{i-1} i^2i^{i-2}\) 这个多项式求exp得到
1 | const int M=1<<18|10,K=17; |